﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace myBST
{
    class BinarySearchTree
    {
        Node Root { get; set; }

        static void Init(string[] args)
        {
            BinarySearchTree bst = new BinarySearchTree();
            bst.Init();
        }

        private void Init()
        {
            Node node1 = new Node { Data = 9 };
            Node node2 = new Node { Data = 2 };
            Node node3 = new Node { Data = 5, Left = new Node { Data = 7 }, Right = node1 };
                  Root = new Node { Data = 4, Left = node2, Right = node3 };

            Console.WriteLine("Breadth First:");
            DisplayMyBF();

            Console.WriteLine("\nDepth First:");
            DisplayMyDF();

            bool exists = IsThere(99);
            Console.WriteLine("\nCheck if value 99 exists: " + exists);
            
        }



        public bool IsThere(int val)
        {
            return IsThere(this.Root, val);
        }

        private bool IsThere(Node rootNode, int val)
        {
            if (rootNode == null)
                return false;
            else if (rootNode.Data == val)
                return true;
            else if (val < rootNode.Data)
                return IsThere(rootNode.Left, val);
            else
                return IsThere(rootNode.Right, val);
        }



        public void DisplayMyBF()
        {
            Queue<Node> q = new Queue<Node>();
            q.Enqueue(Root);

            while (q.Count > 0)
            {
                Node node = q.Dequeue();
                Console.WriteLine(node.Data);
                if (node.Left != null)				
                    q.Enqueue(node.Left);
                
                if (node.Right != null)				
                    q.Enqueue(node.Right);				
            }

        }

        public void DisplayMyDF()
        {
            Stack<Node> s = new Stack<Node>();
            s.Push(Root);

            while (s.Count > 0)
            {
                Node node = s.Pop();
                Console.WriteLine(node.Data);

                if (node.Left != null)				
                    s.Push(node.Left);
                
                if (node.Right != null)				
                    s.Push(node.Right);	

            }
        }


    }
}
